package Single_link

import (
	"fmt"
	"strings"
)

//单链表的接口，
type SingleLink interface {
	GetFirstNode() *SingleLinkNode        // 获取头部节点
	InsertNodeFront(node *SingleLinkNode) //头部节点插入
	InsertNodeBack(node *SingleLinkNode)  // 尾部插入

	InsertNodeValueBack(val interface{}, node *SingleLinkNode) bool  //在某一个节点之前插入元素
	InsertNodeValueFront(val interface{}, node *SingleLinkNode) bool //在某一个节点之后插入元素

	GetNodeAtIndex(index int) *SingleLinkNode ////根据索引抓取指定位置的节点

	DeleteNode(dest *SingleLinkNode) bool //删除一个节点
	DeleteAtindex(index int)              //删除指定位置的节点

	String() string //返回链表的字符串
}

// 链表的结构
type SingleLinkList struct {
	head   *SingleLinkNode //链表的头指针
	length int             //链表的长度
}

//
func NewSingleLinkList() *SingleLinkList {
	node := NewSingleLinkNode(nil)
	return &SingleLinkList{node, 0}
}

//返回第一个数据节点
func (list *SingleLinkList) GetFirstNode() *SingleLinkNode {
	return list.head.pNext
}

//在某一个节点之前插入元素
func (list *SingleLinkList) InsertNodeValueBack(val interface{}, node *SingleLinkNode) bool {
	phead := list.head
	isFind := false //是否找到

	for phead.pNext != nil {
		if phead.val == val {
			isFind = true
			break
		}
		phead = phead.pNext
	}

	if isFind {
		node.pNext = phead.pNext
		phead.pNext = node
		list.length++
		return isFind

	} else {
		return false
	}

}

//在某一个节点之后插入元素
func (list *SingleLinkList) InsertNodeValueFront(val interface{}, node *SingleLinkNode) bool {
	phead := list.head
	isFind := false //是否找到

	for phead.pNext != nil {
		if phead.pNext.val == val {
			isFind = true
			break
		}
		phead = phead.pNext
	}

	if isFind {
		node.pNext = phead.pNext
		phead.pNext = node
		list.length++
		return isFind
	} else {
		return false
	}
}

//头部节点插入
func (list *SingleLinkList) InsertNodeFront(node *SingleLinkNode) {
	if list.head == nil {
		list.head.pNext = node
		node.pNext = nil
		list.length++ //插入节点，数据追加
	} else {
		temp := list.head
		node.pNext = temp.pNext
		temp.pNext = node
		list.length++ //插入节点，数据追加

	}
}

//尾部节点插入
func (list *SingleLinkList) InsertNodeBack(node *SingleLinkNode) {
	if list.head == nil {
		list.head.pNext = node
		node.pNext = nil
		list.length++ //插入节点，数据追加
	} else {
		temp := list.head
		for temp.pNext != nil {
			temp = temp.pNext
		}

		temp.pNext = node
		list.length++
	}
}

// 根据制定索引 返回节点
func (list *SingleLinkList) GetNodeAtIndex(index int) *SingleLinkNode {
	if index > list.length || index < 0 {
		return nil
	} else {
		pHead := list.head

		for index > 0 {
			pHead = pHead.pNext
			index--
		}

		return pHead
	}
}

//删除一个节点
func (list *SingleLinkList) DeleteNode(dest *SingleLinkNode) bool {

	if dest == nil {
		return false
	}

	phead := list.head

	for phead.pNext != nil && phead.pNext != dest {
		phead = phead.pNext
	}

	if phead.pNext == dest {
		phead.pNext = phead.pNext.pNext
		list.length--
		return true
	}

	return false
}

//删除指定位置的节点
func (list *SingleLinkList) DeleteAtindex(index int) bool {

	if index > list.length || index < 0 {
		return false
	} else {
		pHead := list.head

		// pindex = 0

		for index > 0 {

			pHead = pHead.pNext
			index--
		}

		pHead.pNext = pHead.pNext.pNext
		list.length--

		return true
	}

	return false
}

// 输出内容
func (list *SingleLinkList) String() string {
	var listString string

	tmp := list.head
	for tmp.pNext != nil {
		listString += fmt.Sprintf("%v-->", tmp.pNext.val)
		tmp = tmp.pNext
	}

	listString += fmt.Sprintf("nil")

	return listString
}

// 查找字符串
func (list *SingleLinkList) FindString(data string) {

	pHead := list.head.pNext

	for pHead != nil {

		if strings.Contains(pHead.val.(string), data) {
			fmt.Println(pHead.val)
		}

		pHead = pHead.pNext
	}

}

// 求中间的节点
func (list *SingleLinkList) GetMid() *SingleLinkNode {
	if list.head.pNext == nil {
		return nil
	} else {
		pHead1 := list.head
		pHead2 := list.head

		for pHead2 != nil && pHead2.pNext != nil {
			pHead1 = pHead1.pNext
			pHead2 = pHead2.pNext.pNext
		}

		// 返回中间节点
		return pHead1

	}
}

// 反转链表
func (list *SingleLinkList) ReverseList() {

	if list.head == nil || list.head.pNext == nil {
		return ///链表为空或者链表只有一个节点
	} else {
		var pre *SingleLinkNode // 首空节点
		var cur *SingleLinkNode = list.head.pNext

		for cur != nil {
			curNext := cur.pNext // 后续节点
			cur.pNext = pre

			pre = cur     //持续推进
			cur = curNext //持续推进
		}

		//fmt.Println(pre)

		// list.head.pNext.pNext = nil  //
		list.head.pNext = pre

	}

}
